\documentclass[]{lucabeamer}
\usepackage[italian]{babel}
%\usepackage[T1]{fontenc}
%\usepackage{textcomp}
%\usepackage[altbullet]{lucidabr}
\usepackage{graphicx}
\usepackage{epsfig}
\usepackage{url}
\usepackage{mathpartir}
\usepackage{mathbbol}
\usepackage{stmaryrd}
\usepackage{wasysym}
\usepackage{pgfpages}

\usepackage{tikz}
\usetikzlibrary{arrows,shapes}

\input{macros}

\title{Misura della similarit\`a di programmi funzionali mediante isomorfismi di tipi}
\author[]{
  \underline{Silvestri Filippo}
  \and
  Luca Padovani}
\institute[{\ttUniURB}]{
Istituto di Scienze e Tecnologie dell'Informazione, Universit\`a di Urbino
}

\date{23 febbraio 2010}


\begin{document}

\tikzstyle{every picture}+=[remember picture]
\tikzstyle{na} = [baseline=-.5ex]
\tikzstyle{formula} = [inner xsep=0pt,anchor=base]
\everymath{\displaystyle}


\begin{frame}
  \titlepage
\end{frame}


\begin {frame}
\frametitle{\strut Individuazione del plagio}
%\begin{quote}
%  ``Uso non autorizzato del pensiero o del linguaggio di qualche altro autore come se fosse il proprio''\\(Verco and Wise '97)
%\end{quote}}
  \begin{quote}
  ``L'obiettivo \`e individuare file che derivano interamente o \alert{parzialmente} dalla stessa sorgente''\\(Manber '94)
\end{quote}
\end{frame}


\begin{frame}
\frametitle{\strut Smascherare i furbi}
Individuare progetti copiati \alert{NON} significa cercare progetti uguali\\[0,5cm]
\uncover{
\structure{Trasformazioni lessicali}
  \begin{itemize}
    \item aggiunta modifica di commenti
    \item modifiche alla formattazione del testo
    \item modifiche al nome degli identificatori
    \item \dots
  \end{itemize}}
\vfill
\uncover{
\structure{Trasformazioni sintattiche}
  \begin{itemize}
    \item modifiche ai loop
    \item if annidati vs. switch case
    \item chiamata a procedura vs. corpo della procedura
    \item \dots
  \end{itemize}}
\end{frame}


\begin{frame}
\frametitle{\strut Tecniche utilizzate}

\structure{Strumenti lessicali (conteggio di attributi)}\\
\begin{itemize} 
  \item numero di operatori
  \item numero di operandi
  \item numero di linee di codice
  \item numero di istruzioni di controllo
  \item \dots
\end{itemize}
\vfill
\structure{Strumenti sintattici (analisi della struttura)}\\
\begin{itemize}
  \item modifiche ai loop
  \item utilizzo del corpo della funzione al posto della chiamata
  \item \dots
\end{itemize}  
\end{frame}


\begin {frame}
\frametitle{\strut Un nuovo approccio}
\begin{itemize}
\item Individuare l'equivalenza semantica di due programmi \`e un problema indecidibile
\item Bisogna individuare una approssimazione (type checker)
\item Utilizzo del tipo come approssimazione della semantica di una funzione
\end{itemize}
\vfill
\structure{Esempi}
\begin{itemize}
\item succ: $\tint \to \tint$
\item sort: $\alpha\  \tlist \to \alpha\  \tlist$ \hfill 
\end{itemize}
% \begin {center}
% sort [3;2;1]\\
% \alert{sort ``foo''}
% \end{center}
\end{frame}


\begin {frame}
\frametitle{\strut Confronto tra tipi}
\begin{itemize}
\item Necessit\`a di astrarre dalle piccole modifiche del codice sorgente che provocano modifiche ai tipi
\end{itemize}
\vfill
\[
\begin{array}{|c|}
\hline
\text{Strutturale} \\
\hline
f_1: \tchar \to \tstring \to \tbool \\
g_1: \tchar \to \tstring \to \tbool \\
\hline 
\end{array}
\] 
\[
\begin{array}{|c|}
\hline
\text{ ? ? ? } \\
\hline
f_2: \tchar \to \tstring \to \tbool \\
g_2: \tstring \to \tchar \to \tbool \\
\hline
\end{array}
\] 
\end{frame}


\begin {frame}
\frametitle{\strut Isomorfismi di tipi}
\begin{defn}[tipi isomorfi] 
Diciamo che due tipi $A$ e $B$ sono isomorfi, e scriviamo $A \cong B$, se esistono due funzioni $f: A \to B$ e $g: B \to A$ tali che $f \circ g: B \to B = id_B$ e $g \circ f: A \to A = id_A$.
\end{defn}
\vfill
\structure{Esempi}
\begin{itemize}
\item $A \times B \cong B \times A$
\item $A \to B \to C \cong (A \times B) \to C$
\item $A \to B \to C \cong B \to A \to C$
\end{itemize}
\end{frame}


% \begin {frame}
% \frametitle{\strut Isomorfismi di tipi}
% \begin{definition}[tipi isomorfi] 
% Diciamo che due tipi $A$ e $B$ sono isomorfi, e scriviamo $A \cong B$, se esistono due funzioni $f: A \to B$ e $g: B \to A$ tali che $f \circ g: B \to B = id_B$ e $g \circ f: A \to A = id_A$.
% \label{def_iso}
% \end{definition}
% \vfill
% \structure{Esempi}
% \begin{itemize}
% \item $int {\not \cong} char$
% \end{itemize}
% \vfill
% \end{frame}
 
\begin {frame}
\frametitle {\strut Architettura del prototipo}
\begin{figure}
  \begin{center}
    \includegraphics[width=0.8\textwidth]{img/architettura-2.eps}
  \end{center}             
\end{figure}
\end{frame}


\begin {frame}
\frametitle{Applicabilit\`a della teoria}
\structure{Dubbi}\\
\begin{itemize}
\item Poco discriminante? \hfill ...tutti i progetti isomorfi tra loro
\item Troppo discriminante? \hfill ...progetti molto distinti
\end{itemize}
\vfill
\structure{Confronto di 82 progetti funzionali LPC}
  \begin{itemize} 
  \item 32 Tipologia A
  \item 30 Tipologia B
  \item 20 Tipologia C
  \end{itemize}
\end{frame}


\begin{frame}
\frametitle{Applicabilit\`a della teoria}
\begin{figure}
  \centering
  \includegraphics[width=\textwidth]{img/B_Soergel_frequency.eps}
\end{figure}
\end{frame}


\begin {frame}
  \frametitle{Efficacia}
  \begin{figure}
    \begin{center}
      \includegraphics[width=\textwidth]{img/ALL_Soergel_global_scatter_tr_color.eps}
      \end{center}
    \end{figure}
\end{frame}

  
\begin {frame}
\frametitle{Conclusioni}
\begin{itemize}
\item Nuova applicazione degli isomorfismi di tipi
\item Implementazione del tool (applicazione a 82 progetti)
\item Risultati efficaci nell'individuazione del plagio
\item Tempi di esecuzione ragionevoli
  \begin{itemize}
  \item tempo medio calcolo distanza due progetti: $\sim$0.1s
  \item tempo medio calcolo distanza tutti progetti: $\sim$6m
  \end{itemize}
\item Approccio sensibile alle variazioni locali dei tipi
\end{itemize}
\end{frame}


\begin {frame}
  \frametitle{Confronto con tool sintattici}
  \begin{figure}
    \begin{center}
      \includegraphics[width=0.98\textwidth]{img/B_combo_min_cross_BW.eps}
      \end{center}
    \end{figure}
\end{frame}


\begin{frame}
\frametitle{\strut Calcolo della distanza}
\begin{center}
\begin{tabular}{|c|c|c|c|}
  \hline
  \multicolumn{4}{|c|}{Esempio 1:} \\
  \hline 
        & $P_1$ & $P_2$ & $|P_1-P_2|$ \\
  \hline      
  $t_1$ & 0 & 3 & 3 \\
  $t_2$ & 1 & 0 & 1 \\
  \hline
  \multicolumn{4}{|c|}{$D_{P_1,P_2} = 1$} \\
  \hline 
\end{tabular}\ \ \ 
\begin{tabular}{|c|c|c|c|}
  \hline
  \multicolumn{4}{|c|}{Esempio 2:} \\
  \hline 
        & $P_1$ & $P_2$ & $|P_1-P_2|$ \\
  \hline
  $t_1$ & 3 & 3 & 0 \\
  $t_2$ & 1 & 1 & 0 \\
  \hline
  \multicolumn{4}{|c|}{$D_{P_1,P_2} = 0$} \\
  \hline 
\end{tabular}\vfill
\begin{tabular}{|c|c|c|c|}
  \hline
  \multicolumn{4}{|c|}{Esempio 3:} \\
  \hline 
        & $P_1$ & $P_2$ & $|P_1-P_2|$ \\
  \hline
  $t_1$ & 1 & 2 & 1 \\
  $t_2$ & 3 & 2 & 1 \\
  \hline
  \multicolumn{4}{|c|}{$D_{P_1,P_2} = 0.4$} \\
  \hline 
\end{tabular}
\end{center}
\end{frame}


\end{document}
